/*-------------------------------------------------------------------------
 *
 * 伪随机数生成器
 *
 * 我们使用Blackman和Vigna的xoroshiro128** 1.0算法
 * 来生成适合生成合理
 * 好质量64位数据的小型快速PRNG。
 * 然而，这不应被视为
 * 加密强度的。
 *
 * 有关这些生成器的更多信息：https://prng.di.unimi.it/
 * 另请参见https://en.wikipedia.org/wiki/List_of_random_number_generators
 *
 * Copyright (c) 2021-2022, PostgreSQL Global Development Group
 *
 * src/common/pg_prng.c
 *
 *-------------------------------------------------------------------------
 */

#include "c.h"

#include <math.h>				/* 用于 ldexp() */

#include "common/pg_prng.h"
#include "port/pg_bitutils.h"

/* 进程范围的状态向量 */
pg_prng_state pg_global_prng_state;


/*
 * 64 位左旋
 */
static inline uint64 fc_rotl(uint64 fc_x, int fc_bits)
{
	return (fc_x << fc_bits) | (fc_x >> (64 - fc_bits));
}

/*
 * 基本的 xoroshiro128** 算法。
 * 生成并返回一个 64 位均匀分布的数字，
 * 更新下次的状态向量。
 *
 * 注意：状态向量不能全为零，因为那是一个固定点。
 */
static uint64 fc_xoroshiro128ss(pg_prng_state *fc_state)
{
	uint64		fc_s0 = fc_state->s0,
				fc_sx = fc_state->s1 ^ fc_s0,
				fc_val = fc_rotl(fc_s0 * 5, 7) * 9;

	/* 更新状态 */
	fc_state->s0 = fc_rotl(fc_s0, 24) ^ fc_sx ^ (fc_sx << 16);
	fc_state->s1 = fc_rotl(fc_sx, 37);

	return fc_val;
}

/*
 * 我们使用这个生成器仅仅是为了从 64 位种子填充 xoroshiro128** 状态向量。
 */
static uint64 fc_splitmix64(uint64 *fc_state)
{
	/* 状态更新 */
	uint64		fc_val = (*fc_state += UINT64CONST(0x9E3779B97f4A7C15));

	/* 值提取 */
	fc_val = (fc_val ^ (fc_val >> 30)) * UINT64CONST(0xBF58476D1CE4E5B9);
	fc_val = (fc_val ^ (fc_val >> 27)) * UINT64CONST(0x94D049BB133111EB);

	return fc_val ^ (fc_val >> 31);
}

/*
 * 从一个 64 位整数初始化 PRNG 状态，
 * 注意不要产生全零。
 */
void pg_prng_seed(pg_prng_state *fc_state, uint64 fc_seed)
{
	fc_state->s0 = fc_splitmix64(&fc_seed);
	fc_state->s1 = fc_splitmix64(&fc_seed);
	/* 让我们确保没有得到全零。 */
	(void) pg_prng_seed_check(fc_state);
}

/*
 * 从范围 [-1.0, 1.0] 中的双精度数初始化 PRNG 状态，
 * 注意不要产生全零。
 */
void pg_prng_fseed(pg_prng_state *fc_state, double fc_fseed)
{
	/* 假设大约有 52 位尾数位；符号也有贡献。 */
	int64		fc_seed = ((double) ((UINT64CONST(1) << 52) - 1)) * fc_fseed;

	pg_prng_seed(fc_state, (uint64) fc_seed);
}

/*
 * 验证 PRNG 种子值。
 */
bool pg_prng_seed_check(pg_prng_state *fc_state)
{
	/*
	 * 如果种子机制碰巧产生全零，则插入
	 * 一些非零值。任何值都可以；使用 Knuth 的 LCG 参数。
	 */
	if (unlikely(fc_state->s0 == 0 && fc_state->s1 == 0))
	{
		fc_state->s0 = UINT64CONST(0x5851F42D4C957F2D);
		fc_state->s1 = UINT64CONST(0x14057B7EF767814F);
	}

	/* 作为 pg_prng_strong_seed 宏的便利，返回 true */
	return true;
}

/*
 * 从范围 [0, PG_UINT64_MAX] 中均匀选择一个随机 uint64。
 */
uint64 pg_prng_uint64(pg_prng_state *fc_state)
{
	return fc_xoroshiro128ss(fc_state);
}

/*
 * 从范围 [rmin, rmax] 中均匀选择一个随机 uint64。
 * 如果范围为空，总是生成 rmin。
 */
uint64 pg_prng_uint64_range(pg_prng_state *fc_state, uint64 fc_rmin, uint64 fc_rmax)
{
	uint64		fc_val;

	if (likely(fc_rmax > fc_rmin))
	{
		/*
		 * 使用位掩码拒绝方法生成0到范围之间的偏移量。
		 * 每个生成的值都小于两倍的"范围"，因此我们平均
		 * 不应该迭代超过两次。
		 */
		uint64		fc_range = fc_rmax - fc_rmin;
		uint32		fc_rshift = 63 - pg_leftmost_one_pos64(fc_range);

		do
		{
			fc_val = fc_xoroshiro128ss(fc_state) >> fc_rshift;
		} while (fc_val > fc_range);
	}
	else
		fc_val = 0;

	return fc_rmin + fc_val;
}

/*
 * 从范围[PG_INT64_MIN, PG_INT64_MAX]均匀选择一个随机int64。
 */
int64 pg_prng_int64(pg_prng_state *fc_state)
{
	return (int64) fc_xoroshiro128ss(fc_state);
}

/*
 * 从范围[0, PG_INT64_MAX]均匀选择一个随机int64。
 */
int64 pg_prng_int64p(pg_prng_state *fc_state)
{
	return (int64) (fc_xoroshiro128ss(fc_state) & UINT64CONST(0x7FFFFFFFFFFFFFFF));
}

/*
 * 从范围[0, PG_UINT32_MAX]均匀选择一个随机uint32。
 */
uint32 pg_prng_uint32(pg_prng_state *fc_state)
{
	/*
	 * 尽管xoroshiro128**在低位随机性方面没有已知的弱点，
	 * 我们更喜欢在此使用其结果的高位。
	 */
	uint64		fc_v = fc_xoroshiro128ss(fc_state);

	return (uint32) (fc_v >> 32);
}

/*
 * 从范围[PG_INT32_MIN, PG_INT32_MAX]均匀选择一个随机int32。
 */
int32 pg_prng_int32(pg_prng_state *fc_state)
{
	uint64		fc_v = fc_xoroshiro128ss(fc_state);

	return (int32) (fc_v >> 32);
}

/*
 * 从范围[0, PG_INT32_MAX]均匀选择一个随机int32。
 */
int32 pg_prng_int32p(pg_prng_state *fc_state)
{
	uint64		fc_v = fc_xoroshiro128ss(fc_state);

	return (int32) (fc_v >> 33);
}

/*
 * 从范围[0.0, 1.0)均匀选择一个随机double。
 *
 * 注意：如果您想要的结果在范围(0.0, 1.0]内，标准方法
 * 是"1.0 - pg_prng_double(state)"。
 */
double pg_prng_double(pg_prng_state *fc_state)
{
	uint64		fc_v = fc_xoroshiro128ss(fc_state);

	/*
	 * 如上所述，假设double中有52个尾数位。如果双精度的精度
	 * 低于这个值，该结果可能四舍五入为1.0；但我们假设Postgres
	 * 其他地方使用的是IEEE浮点算术，因此这似乎没问题。
	 */
	return ldexp((double) (fc_v >> (64 - 52)), -52);
}

/*
 * 选择一个随机布尔值。
 */
bool pg_prng_bool(pg_prng_state *fc_state)
{
	uint64		fc_v = fc_xoroshiro128ss(fc_state);

	return (bool) (fc_v >> 63);
}
